package Demo1;

public class Partition {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public ListNode partition(ListNode pHead, int x) {
        ListNode ae = null;
        ListNode as = null;
        ListNode be = null;
        ListNode bs = null;

        while (pHead != null){
            if (pHead.val < x){
                if (ae == null){
                    ae = pHead;
                    as = pHead;
                }else{
                    as.next = pHead;
                    as = as.next;
                }
            }else{
                if (be == null){
                    be = pHead;
                    bs = pHead;
                }else {
                    bs.next = pHead;
                    bs = bs.next;
                }
            }
            pHead = pHead.next;
        }

        if (ae == null){
            return be;
        }
        as.next = be;
        if (be != null){
            bs.next = null;
        }
        return ae;
    }
}
